#include <vector>
#include <queue>
#include <iostream>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>> link(n);
        vector<int> degree(n);
        for (vector<int> edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            link[edge[0]].push_back(edge[1]);
            link[edge[1]].push_back(edge[0]);
        }
        queue<int> zero_queue;
        queue<int> queue;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.push(i);
            } else if (degree[i] == 0) {
                zero_queue.push(i);
            }
        }
        if (zero_queue.size() != 0) {
            vector<int> ans;
            while (zero_queue.size() > 0) {
                ans.push_back(zero_queue.front());
                zero_queue.pop();
            }
            return ans;
        }
        while (n > 2) {
            for (int i = 0, len = queue.size(); i < len; i++) {
                int edge = queue.front();
                queue.pop();
                for (int linked : link[edge]) {
                    degree[linked]--;
                    if (degree[linked] == 1) {
                        queue.push(linked);
                    }
                }
                n--;
            }
        }
        vector<int> ans;
        while (queue.size() > 0) {
            ans.push_back(queue.front());
            queue.pop();
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> input = {{0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}};
    Solution solution;
    vector<int> output = solution.findMinHeightTrees(7, input);
    for (int item : output) {
        cout << item << endl;
    }
    return 0;
}